//
// Created by Administrator on 2021/11/3.
// May Saint Diana bless you!
//
#include <vector>
#include <iostream>
#include <stack>

using namespace std;

class Solution {
public:
    /**
     * 求每个格子的储水量
     * 是由当前位置左右的最大值中的较小值决定的
     * 动态规划
     * o(n) ,o(n)
     * @param height
     * @return
     */
    int trap1(vector<int> &height) {
        int n = (int) height.size();
        if (n < 3) return 0;
        // 两个数组，分别储存当前位置左边和右边的最大值
        vector<int> leftMax(n, 0);
        vector<int> rightMax(n, 0);
        leftMax[0] = height[0];
        rightMax.back() = height.back();
        for (int i = 1; i < n; ++i) {
            leftMax[i] = max(leftMax[i - 1], height[i]);
        }
        for (int i = n - 2; i >= 0; --i) {
            rightMax[i] = max(rightMax[i + 1], height[i]);
        }
        int ans = 0;
        // 再遍历一遍数组，得到答案
        for (int i = 0; i < n; ++i) {
            int contri = min(leftMax[i], rightMax[i]) - height[i];
            ans += max(contri, 0);
        }
        return ans;
    }

    /**
     * 用单调递减栈来实现
     * 当前元素比栈顶元素大时，弹栈，此时形成一个低洼，计算这个低洼的面积，加入结果
     * @param height
     * @return
     */
    int trap2(vector<int> &height) {
        stack<int> s; // 栈储存索引
        int i = 0, ans = 0;
        while (i < height.size()) {
            // 当前元素比栈顶元素大
            while (!s.empty() && height[i] > height[s.top()]) {
                int top = s.top();
                s.pop();
                if (s.empty())  // 没有左边界，不用继续判断了
                    break;
                int distance = i - s.top() - 1; // 这段的长度
                int bounded_height = min(height[i], height[s.top()]) - height[top]; // 这段的高度
                ans += distance * bounded_height; // 以面积的形式形成贡献
            }
            s.push(i++);
        }
        return ans;
    }

    /**
     * 双指针实现
     * @param height
     * @return
     */
    int trap3(vector<int> &height) {
        int left = 0, right = (int) height.size() - 1;
        int leftMax = 0, rightMax = 0, ans = 0;
        while (left < right) {
            // 储水量依赖于左边的高度
            if (height[left] < height[right]) {
                if (height[left] > leftMax) {
                    leftMax = height[left];
                } else {
                    ans += leftMax - height[left];
                }
                ++left;
            } else {  // 储水量依赖于右边的高度
                if (height[right] > rightMax) {
                    rightMax = height[right];
                } else {
                    ans += rightMax - height[right];
                }
                --right;
            }
        }
        return ans;
    }
};

int main() {
//    vector<int> height{0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
    vector<int> height{4, 2, 0, 3, 2, 5};
    Solution solution;
    cout << solution.trap1(height) << endl;
    cout << solution.trap2(height) << endl;
    cout << solution.trap3(height) << endl;
    return 0;
}
